package com.zp.self.module.level_4_算法练习.数据结构.二叉树;

import java.util.HashSet;
import java.util.Set;

/**
 * @author By ZengPeng
 */
public class 力扣_653_两数之和IV输入BST {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_653_两数之和IV输入BST().findTarget(TreeNode.initRoot(),32));
    }

    /**
    题目：给定一个二叉搜索树 root 和一个目标结果 k，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。

     示例 1：
     输入: root = [5,3,6,2,4,null,7], k = 9
     输出: true

     示例 2：
     输入: root = [5,3,6,2,4,null,7], k = 28
     输出: false

    分析：【P 💞💓】
       1.Set记录：已有的数，当下一个人查找你时，可以配对
        --执行用时：2 ms, 在所有 Java 提交中击败了95.99%的用户

       官方：ArrayDeque + 左右指针：，左右指针移动值，进行计算 【好复杂】

    边界值 & 注意点：
       1.
     **/
    public boolean findTarget(TreeNode root, int k) {
        Set<Integer> need = new HashSet<>();
        return  dfs(root,k,need);
    }

    private boolean dfs(TreeNode root, int k, Set<Integer> need) {
        if(root==null) return false;
        if(need.contains(k-root.val))
            return true;
        else
            need.add(root.val);
        return dfs(root.right,k,need) || dfs(root.left,k,need);
    }
}
